class LinkedList(object):
def __init__(self):
self.head = None
self.tail = None
self.count = 0
def insertAtStart(self, data):
""" O(1) """
self.count += 1
newNode = Node(data)
if not self.head:
# instantiate a new head node
self.head = newNode
else:
newNode.refNextNode = self.head
self.head = newNode
def size(self):
""" O(1) """
return self.size
def sizeIter(self):
""" O(N) """
currNode = self.head
count = 0
while currNode.refNextNode is not None:
currNode = currNode.refNextNode
count += 1
return count
def insertAtEnd(self, data):
""" O(N) """
if self.head is None:
self.insertAtStart(data)
else:
self.count += 1
currNode = self.head
# find the end of list [O(N)]
while currNode.refNextNode is not None:
currNode = currNode.refNextNode
# create a new node
newNode = Node(data)
currNode.refNextNode = newNode
def remove(self, data):
""" O(N) """
if self.head: # we have elements in the linked list
if data == self.head.data:
self.head = self.head.refNextNode
else:
self.head.removeNode(data, self.head) # O(N)
self.count -= 1
else:
return
def removeIter(self, data):
""" Iterates recursively and removes a given node """
if self.head is None:
return
currNode = self.head
prevNode = None # at the begining
while currNode.data != data:
prevNode, currNode = currNode, currNode.refNextNode
if prevNode is None:
self.head = currNode.refNextNode # update the reference
else:
prevNode.refNextNode = currNode.refNextNode
self.count -= 1
def traverse(self):
""" O(N) """
currNode = self.head
while currNode is not None:
print(currNode.data, end = ",")
currNode = currNode.refNextNode
def __str__(self):
return self